游戏中的学习理论在AI社区中很突出，这是由多个不断上升的应用程序（例如多代理增强学习和生成对抗性网络）的动机。我们提出了突变驱动的乘法更新（M2WU），以在两人零和零正常形式游戏中学习平衡，并证明它在全面和嘈杂的信息反馈设置中都表现出了最后的题融合属性。在全信息反馈设置中，玩家观察了实用程序功能的确切梯度向量。另一方面，在嘈杂的信息反馈设置中，他们只能观察到嘈杂的梯度向量。现有的算法，包括众所周知的乘法权重更新（MWU）和乐观的MWU（OMWU）算法，未能收敛到具有嘈杂的信息反馈的NASH平衡。相反，在两个反馈设置中，M2WU表现出最后的近期收敛到NASH平衡附近的固定点。然后，我们证明它通过迭代地适应突变项来收敛到精确的NASH平衡。我们从经验上确认，M2WU在可剥削性和收敛速率方面胜过MWU和OMWU。
translated by 谷歌翻译
我们考虑使用未知差异的双臂高斯匪徒的固定预算最佳臂识别问题。当差异未知时，性能保证与下限的性能保证匹配的算法最紧密的下限和算法的算法很长。当算法不可知到ARM的最佳比例算法。在本文中，我们提出了一种策略，该策略包括在估计的ARM绘制的目标分配概率之后具有随机采样（RS）的采样规则，并且使用增强的反概率加权（AIPW）估计器通常用于因果推断文学。我们将我们的战略称为RS-AIPW战略。在理论分析中，我们首先推导出鞅的大偏差原理，当第二次孵化的均值时，可以使用，并将其应用于我们提出的策略。然后，我们表明，拟议的策略在错误识别的可能性达到了Kaufmann等人的意义上是渐近最佳的。 （2016）当样品尺寸无限大而双臂之间的间隙变为零。
translated by 谷歌翻译
我们考虑在多武装匪徒问题中拜耳最佳武器识别。假设先前的某些连续性条件，我们表征了贝叶斯简单遗憾的速度。与贝叶斯遗憾的不同（Lai，1987），贝叶斯简单遗憾的主要因素来自最佳和次优臂之间的差距小于$ \ sqrt {\ frac {\ log t} {t}}$。我们提出了一种简单且易于计算的算法，其前导因子与下限达到恒定因子;仿真结果支持我们的理论发现。
translated by 谷歌翻译
我们认为“政策选择”问题 - 否则称为强盗文献中的最佳臂识别 - 由Kasy和Sautmann（2021）提出的适应性实验设计。Kasy和Sautmann（2021）的定理提供了三种渐近结果，为该环境开发的探索采样提供了理论担保。首先表明定理1（1）的证明具有技术问题，定理1（2）的证明和声明是不正确的。然后，我们通过一个反例来展示定理1（3）是假的。对于前两者，我们纠正了陈述并提供严格的证据。对于定理1（3），我们提出了一种替代目标函数，我们称之为后加权政策遗憾，并导出勘探采样的渐近最优性。
translated by 谷歌翻译
我们在随机匪徒上使用时（协变量）信息时，我们研究了固定信道的最佳武器识别问题。虽然我们可以在每轮中使用上下文信息，但我们对在语境分布上的边缘化平均奖励感兴趣。我们的目标是在给定值的错误率下识别最少数量的采样。我们显示出问题的特定实例的示例复杂性下限。然后，我们提出了一个“跟踪和停止”策略的上下文知识版本，其中ARM的比例绘制追踪一组最佳分配，并证明预期的ARM绘制数与渐近的下限匹配。我们证明，与Garivier＆Kaufmann（2016）的结果相比，可以使用上下文信息来提高最佳边缘化平均奖励的效率。我们通过实验证实了上下文信息有助于更快的最佳武器识别。
translated by 谷歌翻译
在本文中，我们在稀疏的随机上下文线性土匪中重新审视了遗憾的最小化问题，其中特征向量可能具有很大的尺寸$ d $，但是奖励功能取决于一些，例如$ s_0 \ ll d $，其中这些功能的这些功能只要。我们提出了阈值拉索匪徒，该算法（i）估算了定义奖励功能及其稀疏支持的向量，即显着特征元素，使用带有阈值的Lasso框架，以及（ii）根据此处选择手臂估计预测其支持。该算法不需要对稀疏索引$ s_0 $的先验知识，并且可以在某些对称假设下不含参数。对于这种简单的算法，我们将非偶然的遗憾上限建立为$ \ mathcal {o}（\ log d + d + \ sqrt {t}）$一般，为$ \ mathcal {o} log t）$在所谓的边缘条件下（手臂奖励分离的概率条件）。以前的算法的遗憾将其缩放为$ \ Mathcal {o}（\ log D + \ \ sqrt {t \ log（d t）}）$和$ \ mathcal {o}（\ log log t \ log t \ log t \ log t \ log d）$设置分别。通过数值实验，我们确认我们的算法优于现有方法。
translated by 谷歌翻译
确定点过程（DPP）的最大后验（MAP）推断对于在许多机器学习应用中选择多种项目至关重要。尽管DPP地图推断是NP-HARD，但贪婪的算法通常会发现高质量的解决方案，许多研究人员已经研究了其有效的实施。一种经典且实用的方法是懒惰的贪婪算法，适用于一般的下函数最大化，而基于Cholesky的最新快速贪婪算法对于DPP MAP推断更有效。本文介绍了如何结合“懒惰”和“快速”的想法，这些思想在文献中被认为是不兼容的。我们懒惰且快速的贪婪算法与当前最好的算法几乎具有相同的时间复杂性，并且在实践中运行速度更快。 “懒惰 +快速”的想法可扩展到其他贪婪型算法。我们还为无约束的DPP地图推断提供了双贪婪算法的快速版本。实验验证了我们加速思想的有效性。
translated by 谷歌翻译
近年来，在许多工业领域引入了机器学习和AI。在诸如金融，医学和自主驾驶的领域，其中模型的推理结果可能具有严重后果，需要高的可解释性以及预测准确性。在这项研究中，我们提出了CGA2M +，其基于广义添加剂2模型（GA2M），并以两种主要方式不同。首先是单调性引入。基于分析师的知识基于某些功能对某些功能进行体重，而且预计不仅可以改善可解释性，而且还改善了概括性表现。第二个是引入高阶项：鉴于Ga2m仅考虑二阶交互，我们旨在通过引入可以捕获更高阶交互的更高阶项来平衡解释性和预测准确性。通过这种方式，我们可以通过应用学习创新来改善预测性能而不会影响可解释性。数值实验表明，该模型具有高预测性能和可解释性。此外，我们证实通过引入单调性来改善泛化性能。
translated by 谷歌翻译